package com.leetcode.demo14;

public class Solution {

    /*//这个函数判断 index 列的字符是否完全相同
    public boolean isSameAtIndex(String[] strs, int index) {
        int i = 0;
        while (i < strs.length - 1) {
            if (strs[i].charAt(index) == strs[i + 1].charAt(index)) {  //不同的串的相同的位置的字母是否相同
                i++;
            } else {
                return false;
            }
        }
        return true;
    }

    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0)
            return "";
        //得到最短的字符串的长度
        int minLength = Integer.MAX_VALUE;
        for (int i = 0; i < strs.length; i++) {
            if (strs[i].length() < minLength) {
                minLength = strs[i].length();   //找出整个字符串数组中的最短的字符串，最长公共子串不可能超过最短的字符串
            }
        }
        int j = 0;
        //遍历所有列
        for (; j < minLength; j++) {
            //如果当前列字符不完全相同，则结束循环
            if (!isSameAtIndex(strs, j)) {
                break;
            }
        }
        return strs[0].substring(0, j);  //不管长度如何，都可以从任意的一个字符串元素中截取j位长度的子串作为最长公共子串，那就取第一个好了

    }*/

    /*public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        //遍历所有列
        for (int i = 0; i < strs[0].length() ; i++){
            char c = strs[0].charAt(i); // 保存 i 列第 0 行的字符便于后续比较
            //比较第 1,2,3... 行的字符和第 0 行是否相等
            for (int j = 1; j < strs.length; j ++) {
                *//**
                 * i == strs[j].length() 表明当前行已经到达末尾
                 * strs[j].charAt(i) != c  当前行和第 0 行字符不相等
                 * 上边两种情况返回结果
                 *//*
                if (i == strs[j].length() || strs[j].charAt(i) != c)
                    return strs[0].substring(0, i);
            }
        }
        return strs[0];
    }*/


    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        return longestCommonPrefix(strs, 0 , strs.length - 1);
    }

    //递归不断分成两部分
    private String longestCommonPrefix(String[] strs, int l, int r) {
        if (l == r) {
            return strs[l];
        }
        else {
            int mid = (l + r)/2;
            String lcpLeft =   longestCommonPrefix(strs, l , mid);
            String lcpRight =  longestCommonPrefix(strs, mid + 1,r);
            return commonPrefix(lcpLeft, lcpRight);
        }
    }
    //求两个结果的最长公共前缀
    String commonPrefix(String left,String right) {
        int min = Math.min(left.length(), right.length());
        for (int i = 0; i < min; i++) {
            if ( left.charAt(i) != right.charAt(i) )
                return left.substring(0, i);
        }
        return left.substring(0, min);
    }

}
